{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Delete the Middle Node of a Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: deleteMiddle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除链表的中间节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个链表的头节点 <code>head</code> 。<strong>删除</strong> 链表的 <strong>中间节点</strong> ，并返回修改后的链表的头节点 <code>head</code> 。</p>\n",
    "\n",
    "<p>长度为 <code>n</code> 链表的中间节点是从头数起第 <code>⌊n / 2⌋</code> 个节点（下标从 <strong>0</strong> 开始），其中 <code>⌊x⌋</code> 表示小于或等于 <code>x</code> 的最大整数。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于 <code>n</code> = <code>1</code>、<code>2</code>、<code>3</code>、<code>4</code> 和 <code>5</code> 的情况，中间节点的下标分别是 <code>0</code>、<code>1</code>、<code>1</code>、<code>2</code> 和 <code>2</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/16/eg1drawio.png\" style=\"width: 500px; height: 77px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,3,4,7,1,2,6]\n",
    "<strong>输出：</strong>[1,3,4,1,2,6]\n",
    "<strong>解释：</strong>\n",
    "上图表示给出的链表。节点的下标分别标注在每个节点的下方。\n",
    "由于 n = 7 ，值为 7 的节点 3 是中间节点，用红色标注。\n",
    "返回结果为移除节点后的新链表。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/16/eg2drawio.png\" style=\"width: 250px; height: 43px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4]\n",
    "<strong>输出：</strong>[1,2,4]\n",
    "<strong>解释：</strong>\n",
    "上图表示给出的链表。\n",
    "对于 n = 4 ，值为 3 的节点 2 是中间节点，用红色标注。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/16/eg3drawio.png\" style=\"width: 150px; height: 58px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [2,1]\n",
    "<strong>输出：</strong>[2]\n",
    "<strong>解释：</strong>\n",
    "上图表示给出的链表。\n",
    "对于 n = 2 ，值为 1 的节点 1 是中间节点，用红色标注。\n",
    "值为 2 的节点 0 是移除节点 1 后剩下的唯一一个节点。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数目在范围 <code>[1, 10<sup>5</sup>]</code> 内</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [delete-the-middle-node-of-a-linked-list](https://leetcode.cn/problems/delete-the-middle-node-of-a-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [delete-the-middle-node-of-a-linked-list](https://leetcode.cn/problems/delete-the-middle-node-of-a-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,4,7,1,2,6]', '[1,2,3,4]', '[2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # if head.next is None:\n",
    "        #     return None\n",
    "        # length = 0\n",
    "        # curr_head = head\n",
    "        # while curr_head:\n",
    "        #     length += 1\n",
    "        #     curr_head = curr_head.next\n",
    "        # target = length // 2\n",
    "        # curr_head = head\n",
    "        # for i in range(target-1):\n",
    "        #     curr_head = curr_head.next\n",
    "        # curr_head.next = curr_head.next.next\n",
    "        # return head\n",
    "\n",
    "        if head.next is None:\n",
    "            return None\n",
    "        slow, fast = head, head.next.next\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        slow.next = slow.next.next\n",
    "        return head\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head.next:\n",
    "            return \n",
    "        \n",
    "        dummy = ListNode(0, head)\n",
    "        pre = dummy\n",
    "        cur = head\n",
    "        count = 1\n",
    "        \n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "            count += 1\n",
    "\n",
    "        count = count // 2\n",
    "\n",
    "        cur = head\n",
    "        while count:\n",
    "            cur = cur.next\n",
    "            pre = pre.next\n",
    "            count -= 1\n",
    "        pre.next = cur.next\n",
    "\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "import math\n",
    "class Solution:\n",
    "    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 双指针\n",
    "        # 方法：直接计数，使用库函数确认中间节点\n",
    "        cur = head\n",
    "        n = 0\n",
    "        while cur:\n",
    "            n += 1\n",
    "            cur = cur.next\n",
    "        mid = math.floor(n/2)\n",
    "        \n",
    "        res = ListNode(0, head)\n",
    "        cur = res\n",
    "        while mid + 1 > 0:\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "            mid -= 1\n",
    "        pre.next = cur.next\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        fast = head\n",
    "        slow = head\n",
    "        pre = slow\n",
    "        if not head.next:\n",
    "            return None\n",
    "        while (fast and fast.next):\n",
    "            pre = slow\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        pre.next = slow.next\n",
    "        return head\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head.next is None:\n",
    "            return None\n",
    "\n",
    "        pre = slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            pre = slow\n",
    "            slow = slow.next\n",
    "        \n",
    "        pre.next = pre.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        new_head = ListNode(-1, head)\n",
    "        fast, slow = head, new_head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        slow.next = slow.next.next\n",
    "        return new_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        new_head = ListNode(-1, head)\n",
    "        fast, slow = head, new_head\n",
    "\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            \n",
    "        slow.next = slow.next.next\n",
    "        return new_head.next"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
